package com.hup.vd.service.netSpeed;

import com.hup.utils.commons.thread.ThreadUtil;
import lombok.extern.slf4j.Slf4j;

import java.util.LinkedList;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

/**
 * 基于滑动窗口算法的RateLimiter,同时也是'简单链表'
 * 实现 {@link #windowSpan} 时间内,限制最大访问次数 {@link #rateLimit};
 * <p>
 * 参考:
 * {@link LinkedList},
 * https://jishuin.proginn.com/p/763bfbd34e5b
 *
 * @author hugan
 * @date 2022/8/14
 * @apiNote 实际效果与 guava.RateLimiter 一样, 建议使用 RateLimiter
 */
@Slf4j
public class SlidingWindowRateLimiter {
    private final ReentrantLock lock = new ReentrantLock();
    private final Condition condition = lock.newCondition();

    /**
     * first:最旧的访问记录,
     * last:最近一次的访问记录
     */
    private Node first, last;
    private int size;

    /**
     * 窗口间隔 1000ms
     */
    private int windowSpan = 1000;
    /**
     * 最大访问次数
     */
    private int rateLimit = 1;

    /**
     * @param rateLimit 必须大于0
     */
    public void setRateLimit(int rateLimit) {
        if (rateLimit < 1) {
            throw new IllegalArgumentException("rateLimit必须大于0");
        }
        this.rateLimit = rateLimit;
    }

    /**
     * 请求一次访问;
     * 如果触发流控,则阻塞线程
     */
    public void acquire() {
        try {
            lock.lock();
            handleAcquire();
        } catch (InterruptedException e) {
            ThreadUtil.handleInterruptedException(e);
        } finally {
            lock.unlock();
        }
    }

    private void handleAcquire() throws InterruptedException {
        if (size == 0 || size < rateLimit) {
            //队列未空或未满, 直接返回
            add(System.currentTimeMillis());
            return;
        }

        //队列已满,移除上个窗口的记录
        long current = System.currentTimeMillis();
        long windowSt = current - windowSpan;//当前窗口的开始时间
        Node toRemove = first;
        int removeCount = 0;
        while (toRemove != null) {
            if (toRemove.accessTime > windowSt) break;
            removeCount++;
            toRemove = toRemove.next;
        }
        if (removeCount > 0) {
            first = toRemove;
            size -= removeCount;
            if (size == 0) last = null;
            //log.info("移除上个窗口的node, 当前size={}, first={}, last={}", size, first, last);
        }

        if (size < rateLimit) {
            //当前窗口期内,队列未满
            add(current);
            return;
        }

        //队列已满
        assert first != null;
        long diff = windowSpan - (current - first.accessTime);
        //log.info("等待={}ms", diff);
        condition.await(diff, TimeUnit.MILLISECONDS);
        //log.info("唤醒={}ms", diff);

        //重新申请,递归调用,要注意无限递归风险;暂时没发现
        handleAcquire();
    }

    private void add(long value) {
        final Node l = last;
        final Node newNode = new Node(value);
        last = newNode;
        if (l == null) first = newNode;
        else l.next = newNode;
        size++;
    }

    private static class Node {
        /**
         * 本次的访问时间
         */
        long accessTime;
        /**
         *
         */
        Node next;

        public Node(long accessTime) {
            this.accessTime = accessTime;
        }

        @Override
        public String toString() {
            return "Node{" + accessTime + '}';
        }
    }

}
